package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-10 00:10
 **/
public class LeetCode748 {

    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] cnt = new int[26];
        for (int i = 0; i < licensePlate.length(); i++) {
            char ch = licensePlate.charAt(i);
            if (Character.isLetter(ch)) {
                ++cnt[Character.toLowerCase(ch) - 'a'];
            }
        }

        //最短补全词索引
        int index = -1;
        for (int i = 0; i < words.length; i++) {
            int[] chars = new int[26];
            for (int j = 0; j < words[i].length(); j++) {
                if (Character.isLetter(words[i].charAt(j))) {
                    ++chars[words[i].charAt(j) - 'a'];
                }
            }

            //是否补全
            boolean flag = true;
            for (int k = 0; k < 26; k++) {
                if (cnt[k] > chars[k]) {
                    flag = false;
                    break;
                }
            }

            if (flag && (index == -1 || words[i].length() < words[index].length())) {
                index = i;
            }
        }
        return words[index];
    }

}
